package com.yx.study.leet.questionList.questions;

import com.yx.study.leet.utils.ListNode;
import org.junit.Test;

/**
 * 24. 两两交换链表中的节点
 * https://leetcode.cn/problems/swap-nodes-in-pairs/
 */
public class SwapPairs24 {
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return head;
        }
        return swap(head);
    }

    private ListNode swap(ListNode head) {
        if (head.next == null) { // 奇数链表直接返回最后一个节点
            return head;
        }
        ListNode next = head.next;
        head.next = head.next.next;
        next.next = head;
        head = next;
        if (head.next.next != null) {
            head.next.next = swap(head.next.next);
        }
        return head;
    }

    @Test
    public void test() {
        // [1,2,3,4]
//        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3,new ListNode(4))));
//        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode listNode = new ListNode(1);
        System.out.println(swapPairs(listNode));
    }

    /**
     * LeetCode官方递归解法
     * 递归代码更加简洁
     * */
    public ListNode swapPairsOffical(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairsOffical(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
